class Solution {
public:
    bool is(string s1,string s2){
        int s = 0;
        for(int i = 0;i < s1.size();i++){
            if(s1[i] != s2[i]){
                s++;
            }
        }
        return s == 1;
    }
    
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordSet(wordList.begin(),wordList.end());
        if(wordSet.find(endWord) == wordSet.end()) return 0;
        
        unordered_map<string,int> ump;
        ump[beginWord] = 1;
        
        queue<int> qe;
        vector<int> used(wordList.size(),0);
        
        for(int i = 0;i < wordList.size();i++){
            if(is(beginWord,wordList[i])){
                qe.push(i);
                used[i] = 1;
                ump[wordList[i]] = 2;
            }
        }
        
        while(!qe.empty()){
            string newWord = wordList[qe.front()];
            qe.pop();
            beginWord = newWord;
            int path = ump[newWord];
            if(beginWord == endWord) return path;
            
            for(int i = 0;i < wordList.size();i++){
                if(used[i] == 1) continue;
                if(is(beginWord,wordList[i])){
                    qe.push(i);
                    used[i] = 1;
                    ump[wordList[i]] = path + 1;
                }
            }
        }
       return 0;
    }
};
